package mao.leetcode.others.leetcode96;

public class Solution {
    public int numTrees(int n) {
        if (n<=1) return 1;
        int[] arr = new int[n+1];
        arr[0]=1;
        arr[1]=1;   //其实arr[1] = arr[0]*arr[0]
        for (int i = 2; i <=n ; i++) {
            for (int j = 0; j <= i-1; j++) {
                arr[i] += arr[j]*arr[i-1-j];
            }
        }
        return arr[n];
    }
    public int numTrees_1(int n) {
        long G=1;
        for (int i = 0; i <  n; i++) {
            G = G*2*(2*i+1)/(i+2);  // G = 2*(2*i+1)/(i+2)*G 不正确，注意计算中间结果可能被截断，精度损失
        }
        return (int)G;
    }
}
